/* 后序非递归遍历二叉树 */

#include <iostream>
#include "BiTreefun.h"
using namespace std;
#define maxsize 50

// 后序非递归遍历
void Nonpost(BTNode *bt)
{
  // 创建栈 -- 存储待访问的结点
  BTNode *St[maxsize], *tag = NULL;
  int top = -1;
  
  // 结点不为空 或者 栈不为空
  while (bt || top != -1)
  {
    // 如果结点不为空
    if (bt != NULL)
    {
      // 进栈
      St[++top] = bt;
      
      // 到左孩子结点
      bt = bt->lchild;
    }
    
    // 如果结点为空
    else
    {
      // 查看栈顶结点
      bt = St[top];
      
      // 如果存在右孩子结点，而且没有被遍历
      if (bt->rchild && bt->rchild != tag)
        bt = bt->rchild; // 到右孩子结点
      
      // 不存在右孩子结点，或者右孩子结点已经被遍历
      else
      {
        // 出栈
        bt = St[top--];
        
        // 打印信息
        cout << bt->data << " ";
        
        // tag记录上一个被访问的结点
        tag = bt;
        bt = NULL;
      }
    }
  }
}

// 后序非递归遍历
void Nonpost2(BTNode *bt)
{
  // 如果结点不为空
  if (bt != NULL)
  {
    // 创建两个栈
    BTNode *Stack1[maxsize];
    BTNode *Stack2[maxsize];
    int top1 = -1, top2 = -1;
    
    // 进1号栈
    Stack1[++top1] = bt;
    
    // 1号栈不为空
    while (top1 != -1)
    {
      // 从1号栈出
      bt = Stack1[top1--];
      
      // 进2号栈
      Stack2[++top2] = bt;
      
      // 左孩子进1号栈
      if (bt->lchild != NULL)
        Stack1[++top1] = bt->lchild;
      
      // 右孩子进1号栈
      if (bt->rchild != NULL)
        Stack1[++top1] = bt->rchild;
    }
    
    // 2号栈不为空
    while (top2 != -1)
    {
      // 出栈，并打印
      bt = Stack2[top2--];
      cout << bt->data << " ";
    }
  }
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  
  // 后序非递归遍历
  Nonpost2(T);
  return 0;
}